package com.base.dataStructure.Tree;

import java.util.LinkedList;

/**
 * @Author: hdhao
 * @Create: 2023/4/5 - 16:09
 * @Version: v1.0
 */
public class TreeTraversal {
    public static void main(String[] args) {
        /*
            1
           / \
          2   3
         /   / \
        4   5   6
         */
        TreeNode root = new TreeNode(1,
                new TreeNode(2,
                        new TreeNode(4, null, null),
                        null),
                new TreeNode(3,
                        new TreeNode(5, null, null),
                        new TreeNode(6, null, null)));
        /*preOrder(root);
        System.out.println();
        inOrder(root);
        System.out.println();
        postOrder(root);*/
        LinkedList<TreeNode> stack = new LinkedList<>();
        //代表当前节点
        TreeNode curr = root;
        //最近一次弹栈的元素
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                System.out.println("去：" + curr.val);
                //为了记住回来的路(压入栈)
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();//栈顶元素
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                    System.out.println("回：" + pop.val);
                } else {
                    curr = peek.right;
                }
            }
        }
    }

    //---------------------递归实现------------------//

    /**
     * 前序遍历
     *
     * @param node
     */
    static void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + "\t");
        //左子树
        preOrder(node.left);
        //右子树
        preOrder(node.right);
    }

    /**
     * 中序遍历
     *
     * @param node
     */
    static void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.val + "\t");
        inOrder(node.right);
    }

    /**
     * 后序遍历
     *
     * @param node
     */
    static void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val + "\t");
    }

    //---------------------非递归实现------------------//

    /**
     * 前序遍历
     *
     * @param node
     */
    static void preOrder1(TreeNode node) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        //代表当前节点
        TreeNode curr = node;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                System.out.println("去：" + curr.val);
                //为了记住回来的路(压入栈)
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode pop = stack.pop();
//                System.out.println("回：" + pop.val);
                curr = pop.right;
            }
        }
    }


    /**
     * 中序遍历
     *
     * @param node
     */
    static void inOrder1(TreeNode node) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        //代表当前节点
        TreeNode curr = node;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
//                System.out.println("去：" + curr.val);
                //为了记住回来的路(压入栈)
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode pop = stack.pop();
                System.out.println("回：" + pop.val);
                curr = pop.right;
            }
        }
    }

    /**
     * 后序遍历
     *
     * @param node
     */
    static void postOrder1(TreeNode node) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        //代表当前节点
        TreeNode curr = node;
        //最近一次弹栈的元素
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                System.out.println("去：" + curr.val);
                //为了记住回来的路(压入栈)
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();//栈顶元素
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                    System.out.println("回：" + pop.val);
                } else {
                    curr = peek.right;
                }
            }
        }
    }

    /**
     * 通用(注意打印时机)
     *
     * @param node
     */
    static void postOrder2(TreeNode node) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        //代表当前节点
        TreeNode curr = node;
        //最近一次弹栈的元素
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                //为了记住回来的路(压入栈)
                stack.push(curr);
                //前序遍历打印时机
                System.out.println(curr.val);
                //处理左子树
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();//栈顶元素
                //没有右子树
                if (peek.right == null) {
                    //中序遍历打印时机
                    System.out.println(pop.val);
                    pop = stack.pop();
                    //后序遍历打印时机
                    System.out.println(pop.val);
                } else if(peek.right == pop) {//右子树已经处理完成了
                    pop = stack.pop();
                    //后序遍历打印时机
                    System.out.println(pop.val);
                } else {
                    //终于遍历打印时机
                    System.out.println(peek.val);
                    //处理右子树
                    curr = peek.right;
                }
            }
        }
    }
}
